# 火车运输
"""本题是典型的01背包问题的变种, 可以参考 ./leetcode/dp/knapsack_01 问题"""
import sys


def max_transport_weight_dp(alpha, beta, weights):
    """
    优化前的通过率 13/20
    优化之后的通过率 18/20
    dp算法, 典型的01背包问题的解法
    dp[i][j]
    :param alpha: 车厢A的能装载的最大重量
    :param beta: 车厢B的能装载的最大重量
    :param weights: 物品的重量数组
    :return: 车厢A和车厢B的可以装载的最大重量
    """
    dp = [[0] * (alpha + 1) for _ in range(beta + 1)]
    max_weight = alpha + beta

    for weight in weights:
        for i in range(beta, -1, -1):
            for j in range(alpha, -1, -1):
                if weight > i and weight > j:  # 重量大于i和j, 跳过
                    break
                elif weight <= i and weight <= j:  # 重量小于i和j需要判断: 放入A车厢/放入B车厢/都不放
                    dp[i][j] = max(dp[i][j], dp[i - weight][j] + weight, dp[i][j - weight] + weight)
                elif weight <= i:  # 重量只小于i
                    dp[i][j] = max(dp[i][j], dp[i - weight][j] + weight)
                else:  # 重量只小于j
                    dp[i][j] = max(dp[i][j], dp[i][j - weight] + weight)
                if dp[i][j] == max_weight:  # 优化: 如果达到最大值就直接返回
                    return max_weight
    return dp[beta][alpha]


def max_transport_weight_dfs(alpha, beta, weights):
    """回溯法, 暴力解法
    优化前: 6/20
    优化后: 20/20
    """
    res = 0
    n = len(weights)

    def backtrack(curr_a, curr_b, idx):
        nonlocal res
        if curr_a == alpha and curr_b == beta:  # 优化: 达到最大值就直接退出程序
            res = curr_a + curr_b
            print(res)
            sys.exit()
        if curr_a > alpha or curr_b > beta:
            return
        if idx == n:
            res = max(res, curr_a + curr_b)
            return

        # a 选择当前物品
        if alpha - curr_a >= weights[idx]:
            backtrack(curr_a + weights[idx], curr_b, idx + 1)
        # b 选择当前物品
        if beta - curr_b >= weights[idx]:
            backtrack(curr_a, curr_b + weights[idx], idx + 1)
        # 都不选择
        backtrack(curr_a, curr_b, idx + 1)

    backtrack(0, 0, 0)
    return res


if __name__ == '__main__':
    # n, a, b = map(int, input().split())
    # weights = list(map(int, input().split()))
    a, b = 10, 8
    weights = [8, 9, 1]
    print(max_transport_weight_dp(a, b, weights))
    print(max_transport_weight_dfs(a, b, weights))
